/**
 * 
 */
package logic.algorithm;

import java.util.LinkedList;
import java.util.Queue;

import datamodel.Grid;
import datamodel.GridElement;
import datamodel.GridElementAlgoState;
import datamodel.GridElementState;

/**
 * @author Magnus, Kevin Munk
 * @version 0.1
 *
 */
public class Moore implements Algorithm {
	
	private Grid grid;

	
	private Queue<GridElement> w = new LinkedList<GridElement>();
	private Queue<GridElement> neighbors = new LinkedList<GridElement>();

	/* (non-Javadoc)
	 * @see logic.algorithm.Algorithm#init(datamodel.Grid)
	 */
	@Override
	public void init(Grid grid) {
		this.grid = grid;

		// First, set up the grid by marking all nodes as unvisited, setting their distances to the max value
		// and setting all predecessors to null
		for (int row = 0; row < this.grid.getRows(); row++){
			for (int column = 0; column < this.grid.getColumns(); column++){
				this.grid.getElementAt(row, column).setDistance(Integer.MAX_VALUE);
				this.grid.getElementAt(row, column).setAlgoState(GridElementAlgoState.NONE);
				this.grid.getElementAt(row, column).setPredecessor(null);
			}
		}
		// Then, set the start node to 0 distance and mark
		this.grid.getStartElement().setDistance(0);
		// We start from here to add it to the queue.
		w.add(this.grid.getStartElement());
	}

	/* (non-Javadoc)
	 * @see logic.algorithm.Algorithm#doNextStep()
	 */
	@Override
	public boolean doNextStep() {
		// Implementation idea:
		// Use two queues. The first queue stores the nodes whose neighbors should be examined.
		//				   The second queue stores the neighbors to be examined.
		// In each call do doNextStep() we take one neighbor and examine it.
		// (Before that, we have to make sure that there is a neighbor.) 

		if(isSolved())
			return false;
		
		// Each call to doNextStep() examines one neighbor of the current node.
		// Make sure there are neighbors.
		while(neighbors.isEmpty()) {
			if(w.isEmpty()) // Cannot fill neighbors queue again. Terminate
				return false;
			// Fill neighbors queue.
			for(GridElement ge : grid.getNeighborsFrom(w.element(), false).getNeighbors()) {
				if(ge!=null &&
				   ge.getDistance() == Integer.MAX_VALUE && // Has not been visited
				   (ge.getState() == GridElementState.START || ge.getState() == GridElementState.END
				    || ge.getState() == GridElementState.FREE)) // Is not a BLOCKED GridElement
						neighbors.add(ge);
			}
			// No neighbors were found that match the criteria.
			if(neighbors.isEmpty()) {
				w.remove();
			}
				
		}
	
		// we have neighbors
		// Take one 
		GridElement n = neighbors.remove();
		// n != null (Guarantee above)
		// Sets distance and LOOKED_AT flag.
		n.setDistance(w.element().getDistance() + 4);
		n.setPredecessor(w.element());
		// Remember it. We will advance to this neighbor in the future and explore its neighbors.
		w.add(n);
	
		
		return true;
	}

	/* (non-Javadoc)
	 * @see logic.algorithm.Algorithm#isSolved()
	 */
	@Override
	public boolean isSolved() {
		return grid.getEndElement().getDistance() != Integer.MAX_VALUE;
	}

}
